`:top

In `F33f`_`[descriptive complexity`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Descriptive_complexity]`_`f, a `!query`! is a mapping from structures of one `F33f`_`[signature`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Signature_(logic)]`_`f to structures of another vocabulary. `F33f`_`[Neil Immerman`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Neil_Immerman]`_`f, in his book Descriptive Complexity,`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] "use[s] the concept of query as the fundamental paradigm of computation" (p. 17).

Given signatures σ σ {\\displaystyle \\sigma } and τ τ {\\displaystyle \\tau } , we define the set of `F33f`_`[structures`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Structure_(mathematical_logic)]`_`f on each language, STRUC [ σ σ ] {\\displaystyle {\\mbox{STRUC}}[\\sigma ]} and STRUC [ τ τ ] {\\displaystyle {\\mbox{STRUC}}[\\tau ]} . A query is then any mapping

`*I : STRUC [ σ σ ] → → STRUC [ τ τ ] {\\displaystyle I:{\\mbox{STRUC}}[\\sigma ]\\to {\\mbox{STRUC}}[\\tau ]}`*

`F33f`_`[Computational complexity theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_complexity_theory]`_`f can then be phrased in terms of the power of the mathematical logic necessary to express a given query.

>>Contents

• `F0af`_`[Order-independent queries`#order-independent-queries]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>Order-independent queries

A query is `!order-independent`! if the ordering of objects in the structure does not affect the results of the query. In databases, these queries correspond to generic queries (Immerman 1999, p. 18). A query is order-independent iff I ( A ) ≡ ≡ I ( B ) {\\displaystyle I({\\mathfrak {A}})\\equiv I({\\mathfrak {B}})} for any isomorphic structures A {\\displaystyle {\\mathfrak {A}}} and B {\\displaystyle {\\mathfrak {B}}} .

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefneil1999`aNeil, Immerman (1999). `F33f`_`[Descriptive Complexity`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Descriptive_Complexity]`_`f. New York, NY: Springer New York. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 9781461205395. `F33f`_`[OCLC`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=OCLC_(identifier)]`_`f 853271745.

`c`F0af`_`[↑ Back to top`#top]`_`f`a